Search Results

Documents authored by Kuhn, Fabian

Document
DOI: 10.4230/LIPIcs.DISC.2023.7
On the Node-Averaged Complexity of Locally Checkable Problems on Trees

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Gustav Schmid

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminating in an almost-complete classification on general graphs and a complete classification on trees. The latter states that, on bounded-degree trees, any LCL problem has deterministic worst-case time complexity O(1), Θ(log^* n), Θ(log n), or Θ(n^{1/k}) for some positive integer k, and all of those complexity classes are nonempty. Moreover, randomness helps only for (some) problems with deterministic worst-case complexity Θ(log n), and if randomness helps (asymptotically), then it helps exponentially. In this work, we study how many distributed rounds are needed on average per node in order to solve an LCL problem on trees. We obtain a partial classification of the deterministic node-averaged complexity landscape for LCL problems. As our main result, we show that every problem with worst-case round complexity O(log n) has deterministic node-averaged complexity O(log^* n). We further establish bounds on the node-averaged complexity of problems with worst-case complexity Θ(n^{1/k}): we show that all these problems have node-averaged complexity Ω̃(n^{1 / (2^k - 1)}), and that this lower bound is tight for some problems.
Cite as

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Gustav Schmid. On the Node-Averaged Complexity of Locally Checkable Problems on Trees. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2023.7,
  author =	{Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis and Schmid, Gustav},
  title =	{{On the Node-Averaged Complexity of Locally Checkable Problems on Trees}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.7},
  URN =		{urn:nbn:de:0030-drops-191330},
  doi =		{10.4230/LIPIcs.DISC.2023.7},
  annote =	{Keywords: distributed graph algorithms, locally checkable labelings, node-averaged complexity, trees}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.11
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Authors: Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
In this work, we present a constant-round algorithm for the 2-ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear space-per-machine and optimal total space. Our results improve on the O(log log log n)-round algorithm by [HPS, DISC'14] and the O(log log Δ)-round algorithm by [GGKMR, PODC'18]. Our techniques can also be applied to the semi-streaming model to obtain an O(1)-pass algorithm. Our main technical contribution is a novel sampling procedure that returns a small subgraph such that almost all nodes in the input graph are adjacent to the sampled subgraph. An MIS on the sampled subgraph provides a 2-ruling set for a large fraction of the input graph. As a technical challenge, we must handle the remaining part of the graph, which might still be relatively large. We overcome this challenge by showing useful structural properties of the remaining graph and show that running our process twice yields a 2-ruling set of the original input graph with high probability.
Cite as

Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cambus_et_al:LIPIcs.DISC.2023.11,
  author =	{Cambus, M\'{e}lanie and Kuhn, Fabian and Pai, Shreyas and Uitto, Jara},
  title =	{{Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.11},
  URN =		{urn:nbn:de:0030-drops-191378},
  doi =		{10.4230/LIPIcs.DISC.2023.11},
  annote =	{Keywords: Ruling Sets, Parallel Algorithms, Congested Clique, Massively Parallel Computing, Semi-Streaming}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.22
List Defective Colorings: Distributed Algorithms and Applications

Authors: Marc Fuchs and Fabian Kuhn

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
The distributed coloring problem is at the core of the area of distributed graph algorithms and it is a problem that has seen tremendous progress over the last few years. Much of the remarkable recent progress on deterministic distributed coloring algorithms is based on two main tools: a) defective colorings in which every node of a given color can have a limited number of neighbors of the same color and b) list coloring, a natural generalization of the standard coloring problem that naturally appears when colorings are computed in different stages and one has to extend a previously computed partial coloring to a full coloring. In this paper, we introduce list defective colorings, which can be seen as a generalization of these two coloring variants. Essentially, in a list defective coloring instance, each node v is given a list of colors x_{v,1},… ,x_{v,p} together with a list of defects d_{v,1},… ,d_{v,p} such that if v is colored with color x_{v, i}, it is allowed to have at most d_{v, i} neighbors with color x_{v, i}. We highlight the important role of list defective colorings by showing that faster list defective coloring algorithms would directly lead to faster deterministic (Δ+1)-coloring algorithms in the LOCAL model. Further, we extend a recent distributed list coloring algorithm by Maus and Tonoyan [DISC '20]. Slightly simplified, we show that if for each node v it holds that ∑_{i=1}^p (d_{v,i}+1)² > deg_G²(v)⋅ polylogΔ then this list defective coloring instance can be solved in a communication-efficient way in only O(logΔ) communication rounds. This leads to the first deterministic (Δ+1)-coloring algorithm in the standard CONGEST model with a time complexity of O(√{Δ}⋅ polylog Δ+log^* n), matching the best time complexity in the LOCAL model up to a polylogΔ factor.
Cite as

Marc Fuchs and Fabian Kuhn. List Defective Colorings: Distributed Algorithms and Applications. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.DISC.2023.22,
  author =	{Fuchs, Marc and Kuhn, Fabian},
  title =	{{List Defective Colorings: Distributed Algorithms and Applications}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.22},
  URN =		{urn:nbn:de:0030-drops-191484},
  doi =		{10.4230/LIPIcs.DISC.2023.22},
  annote =	{Keywords: distributed coloring, list coloring, defective coloring}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.28
Routing Schemes and Distance Oracles in the Hybrid Model

Authors: Fabian Kuhn and Philipp Schneider

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
The HYBRID model was introduced as a means for theoretical study of distributed networks that use various communication modes. Conceptually, it is a synchronous message passing model with a local communication mode, where in each round each node can send large messages to all its neighbors in a local network (a graph), and a global communication mode, where each node is allotted limited (polylogarithmic) bandwidth per round to communicate with any node in the network. Prior work has often focused on shortest paths problems in the local network, as their global nature makes these an interesting case study how combining communication modes in the HYBRID model can overcome the individual lower bounds of either mode. In this work we consider a similar problem, namely computation of distance oracles and routing schemes. In the former, all nodes have to compute local tables, which allows them to look up the distance (estimates) to any target node in the local network when provided with the label of the target. In the latter, it suffices that nodes give the next node on an (approximately) shortest path to the target. Our goal is to compute these local tables as fast as possible with labels as small as possible. We show that this can be done exactly in Õ(n^{1/3}) communication rounds and labels of size Θ(n^{2/3}) bits. For constant stretch approximations we achieve labels of size O(log n) in the same time. Further, as our main technical contribution, we provide computational lower bounds for a variety of problem parameters. For instance, we show that computing solutions with stretch below a certain constant takes Ω̃(n^{1/3}) rounds even for labels of size O(n^{2/3}).
Cite as

Fabian Kuhn and Philipp Schneider. Routing Schemes and Distance Oracles in the Hybrid Model. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 28:1-28:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kuhn_et_al:LIPIcs.DISC.2022.28,
  author =	{Kuhn, Fabian and Schneider, Philipp},
  title =	{{Routing Schemes and Distance Oracles in the Hybrid Model}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{28:1--28:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.28},
  URN =		{urn:nbn:de:0030-drops-172198},
  doi =		{10.4230/LIPIcs.DISC.2022.28},
  annote =	{Keywords: Distributed Computing, Graph Algorithms, Complexity Analysis}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2022.3
Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring (Invited Talk)

Authors: Fabian Kuhn

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
The problem of obtaining fast deterministic algorithms for distributed symmetry breaking problems in graphs has long been considered one of the most challenging problems in the area of distributed graph algorithms. Consider for example the distributed coloring problem, where a (computer) network is modeled by an arbitrary graph G = (V,E) and the objective is to compute a vertex coloring of G by running a distributed algorithm on the graph G. It is maybe not surprising that randomization can be a helpful tool to efficiently compute such a coloring. In fact, as long as each node v ∈ V can choose among deg(v)+1 different colors, even an almost trivial algorithm in which all nodes keep trying a random available color allows to color all nodes in O(log n) parallel steps. How to obtain a similarly efficient deterministic distributed coloring algorithm is far less obvious. In fact, for a long time, there has been an exponential gap between the time complexities of the best randomized and the best deterministic distributed algorithms for various graph coloring variants and for many other basic graph problems. In the last few years, there however has been substantial progress on deterministic distributed graph algorithms that are nearly as fast as randomized algorithms for the same tasks. In particular, in a recent breakthrough, Rozhoň and Ghaffari managed to reduce the gap between the randomized and deterministic complexities of locally checkable graph problems to at most polylog n. In the talk, we give a brief overview of the history of the problem of finding fast deterministic algorithms for distributed symmetry breaking problems and of what we know about the relation between deterministic and randomized distributed algorithms for such problems. Together with some additional recent developments, the result of Rozhoň and Ghaffari provides a generic, somewhat brute-force way to efficiently derandomize randomized distributed algorithms. Apart from this, there has also been substantial progress on more direct, problem-specific algorithms. In the talk, we in particular discuss some novel deterministic distributed graph coloring algorithms. The algorithms are signficantly faster and we believe also simpler than previous algorithms for the same coloring problems.
Cite as

Fabian Kuhn. Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring (Invited Talk). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kuhn:LIPIcs.STACS.2022.3,
  author =	{Kuhn, Fabian},
  title =	{{Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.3},
  URN =		{urn:nbn:de:0030-drops-158131},
  doi =		{10.4230/LIPIcs.STACS.2022.3},
  annote =	{Keywords: distributed graph algorithms, derandomization, distributed coloring}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.11
Near-Shortest Path Routing in Hybrid Communication Networks

Authors: Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the HYBRID model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with each neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the HYBRID model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with n nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size O(log n) bits in only O(log n) rounds.
Cite as

Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs. Near-Shortest Path Routing in Hybrid Communication Networks. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coy_et_al:LIPIcs.OPODIS.2021.11,
  author =	{Coy, Sam and Czumaj, Artur and Feldmann, Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp and Struijs, Martijn},
  title =	{{Near-Shortest Path Routing in Hybrid Communication Networks}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.11},
  URN =		{urn:nbn:de:0030-drops-157863},
  doi =		{10.4230/LIPIcs.OPODIS.2021.11},
  annote =	{Keywords: Hybrid networks, overlay networks}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.17
Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Authors: Salwa Faour, Marc Fuchs, and Fabian Kuhn

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
We provide CONGEST model algorithms for approximating the minimum weighted vertex cover and the maximum weighted matching problem. For bipartite graphs, we show that a (1+ε)-approximate weighted vertex cover can be computed deterministically in poly((log n)/ε) rounds. This generalizes a corresponding result for the unweighted vertex cover problem shown in [Faour, Kuhn; OPODIS '20]. Moreover, we show that in general weighted graph families that are closed under taking subgraphs and in which we can compute an independent set of weight at least λ⋅ w(V) (where w(V) denotes the total weight of all nodes) in polylogarithmic time in the CONGEST model, one can compute a (2-2λ +ε)-approximate weighted vertex cover in poly((log n)/ε) rounds in the CONGEST model. Our result in particular implies that in graphs of arboricity a, one can compute a (2-1/a+ε)-approximate weighted vertex cover problem in poly((log n)/ε) rounds in the CONGEST model. For maximum weighted matchings, we show that a (1-ε)-approximate solution can be computed deterministically in time 2^{O(1/ε)}⋅ polylog n in the CONGEST model. We also provide a randomized algorithm that with arbitrarily good constant probability succeeds in computing a (1-ε)-approximate weighted matching in time 2^{O(1/ε)}⋅ polylog(Δ W)⋅ log^* n, where W denotes the ratio between the largest and the smallest edge weight. Our algorithm generalizes results of [Lotker, Patt-Shamir, Pettie; SPAA '08] and [Bar-Yehuda, Hillel, Ghaffari, Schwartzman; PODC '17], who gave 2^{O(1/ε)}⋅ log n and 2^{O(1/ε)}⋅ (logΔ)/(log logΔ)-round randomized approximations for the unweighted matching problem. Finally, we show that even in the LOCAL model and in bipartite graphs of degree ≤ 3, if ε < ε₀ for some constant ε₀ > 0, then computing a (1+ε)-approximation for the unweighted minimum vertex cover problem requires Ω((log n)/ε) rounds. This generalizes a result of [Göös, Suomela; DISC '12], who showed that computing a (1+ε₀)-approximation in such graphs requires Ω(log n) rounds.
Cite as

Salwa Faour, Marc Fuchs, and Fabian Kuhn. Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{faour_et_al:LIPIcs.OPODIS.2021.17,
  author =	{Faour, Salwa and Fuchs, Marc and Kuhn, Fabian},
  title =	{{Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.17},
  URN =		{urn:nbn:de:0030-drops-157928},
  doi =		{10.4230/LIPIcs.OPODIS.2021.17},
  annote =	{Keywords: distributed graph algorithms, minimum weighted vertex cover, maximum weighted matching, distributed optimization, CONGEST model}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.18
Improved Distributed Fractional Coloring Algorithms

Authors: Alkida Balliu, Fabian Kuhn, and Dennis Olivetti

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
We prove new bounds on the distributed fractional coloring problem in the LOCAL model. A fractional c-coloring of a graph G = (V,E) is a fractional covering of the nodes of G with independent sets such that each independent set I of G is assigned a fractional value λ_I ∈ [0,1]. The total value of all independent sets of G is at most c, and for each node v ∈ V, the total value of all independent sets containing v is at least 1. Equivalently, fractional c-colorings can also be understood as multicolorings as follows. For some natural numbers p and q such that p/q ≤ c, each node v is assigned a set of at least q colors from {1,…,p} such that adjacent nodes are assigned disjoint sets of colors. The minimum c for which a fractional c-coloring of a graph G exists is called the fractional chromatic number χ_f(G) of G. Recently, [Bousquet, Esperet, and Pirot; SIROCCO '21] showed that for any constant ε > 0, a fractional (Δ+ε)-coloring can be computed in Δ^{O(Δ)} + O(Δ⋅log^* n) rounds. We show that such a coloring can be computed in only O(log² Δ) rounds, without any dependency on n. We further show that in O((log n)/ε) rounds, it is possible to compute a fractional (1+ε)χ_f(G)-coloring, even if the fractional chromatic number χ_f(G) is not known. That is, the fractional coloring problem can be approximated arbitrarily well by an efficient algorithm in the LOCAL model. For the standard coloring problem, it is only known that an O((log n)/(log log n))-approximation can be computed in polylogarithmic time in the LOCAL model. We also show that our distributed fractional coloring approximation algorithm is best possible. We show that in trees, which have fractional chromatic number 2, computing a fractional (2+ε)-coloring requires at least Ω((log n)/ε) rounds. We finally study fractional colorings of regular grids. In [Bousquet, Esperet, and Pirot; SIROCCO '21], it is shown that in regular grids of bounded dimension, a fractional (2+ε)-coloring can be computed in time O(log^* n). We show that such a coloring can even be computed in O(1) rounds in the LOCAL model.
Cite as

Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. Improved Distributed Fractional Coloring Algorithms. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.OPODIS.2021.18,
  author =	{Balliu, Alkida and Kuhn, Fabian and Olivetti, Dennis},
  title =	{{Improved Distributed Fractional Coloring Algorithms}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.18},
  URN =		{urn:nbn:de:0030-drops-157935},
  doi =		{10.4230/LIPIcs.OPODIS.2021.18},
  annote =	{Keywords: distributed graph algorithms, distributed coloring, locality, fractional coloring}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.29
Approximating Bipartite Minimum Vertex Cover in the CONGEST Model

Authors: Salwa Faour and Fabian Kuhn

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
We give efficient distributed algorithms for the minimum vertex cover problem in bipartite graphs in the CONGEST model. From Kőnig’s theorem, it is well known that in bipartite graphs the size of a minimum vertex cover is equal to the size of a maximum matching. We first show that together with an existing O(nlog n)-round algorithm for computing a maximum matching, the constructive proof of Kőnig’s theorem directly leads to a deterministic O(nlog n)-round CONGEST algorithm for computing a minimum vertex cover. We then show that by adapting the construction, we can also convert an approximate maximum matching into an approximate minimum vertex cover. Given a (1-δ)-approximate matching for some δ > 1, we show that a (1+O(δ))-approximate vertex cover can be computed in time O (D+poly((log n)/δ)), where D is the diameter of the graph. When combining with known graph clustering techniques, for any ε ∈ (0,1], this leads to a poly((log n)/ε)-time deterministic and also to a slightly faster and simpler randomized O((log n)/ε³)-round CONGEST algorithm for computing a (1+ε)-approximate vertex cover in bipartite graphs. For constant ε, the randomized time complexity matches the Ω(log n) lower bound for computing a (1+ε)-approximate vertex cover in bipartite graphs even in the LOCAL model. Our results are also in contrast to the situation in general graphs, where it is known that computing an optimal vertex cover requires Ω̃(n²) rounds in the CONGEST model and where it is not even known how to compute any (2-ε)-approximation in time o(n²).
Cite as

Salwa Faour and Fabian Kuhn. Approximating Bipartite Minimum Vertex Cover in the CONGEST Model. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{faour_et_al:LIPIcs.OPODIS.2020.29,
  author =	{Faour, Salwa and Kuhn, Fabian},
  title =	{{Approximating Bipartite Minimum Vertex Cover in the CONGEST Model}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.29},
  URN =		{urn:nbn:de:0030-drops-135149},
  doi =		{10.4230/LIPIcs.OPODIS.2020.29},
  annote =	{Keywords: distributed vertex cover, distributed graph algorithms, distributed optimization, bipartite vertex cover}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.37
Distributed Maximum Matching Verification in CONGEST

Authors: Mohamad Ahmadi and Fabian Kuhn

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We study the maximum cardinality matching problem in a standard distributed setting, where the nodes V of a given n-node network graph G = (V,E) communicate over the edges E in synchronous rounds. More specifically, we consider the distributed CONGEST model, where in each round, each node of G can send an O(log n)-bit message to each of its neighbors. We show that for every graph G and a matching M of G, there is a randomized CONGEST algorithm to verify M being a maximum matching of G in time O(|M|) and disprove it in time O(D + 𝓁), where D is the diameter of G and 𝓁 is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time Õ(s^*), where s^* is the size of a maximum matching.
Cite as

Mohamad Ahmadi and Fabian Kuhn. Distributed Maximum Matching Verification in CONGEST. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.DISC.2020.37,
  author =	{Ahmadi, Mohamad and Kuhn, Fabian},
  title =	{{Distributed Maximum Matching Verification in CONGEST}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.37},
  URN =		{urn:nbn:de:0030-drops-131151},
  doi =		{10.4230/LIPIcs.DISC.2020.37},
  annote =	{Keywords: distributed matching, distributed graph algorithms, augmenting paths}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.39
Coloring Fast Without Learning Your Neighbors' Colors

Authors: Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}.
Cite as

Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin. Coloring Fast Without Learning Your Neighbors' Colors. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.DISC.2020.39,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Kuhn, Fabian and Maus, Yannic and Nolin, Alexandre},
  title =	{{Coloring Fast Without Learning Your Neighbors' Colors}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.39},
  URN =		{urn:nbn:de:0030-drops-131170},
  doi =		{10.4230/LIPIcs.DISC.2020.39},
  annote =	{Keywords: distributed graph coloring, distance 2 coloring, congestion}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.53
Concurrent Distributed Serving with Mobile Servers

Authors: Abdolhamid Ghodselahi, Fabian Kuhn, and Volker Turau

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are k identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol Gnn that solves the DSMS problem on overlay trees. We prove that Gnn is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze Gnn for "one-shot" executions, i.e., all requests are invoked simultaneously. We prove that when running Gnn on top of a special family of tree topologies - known as hierarchically well-separated trees (HSTs) - we obtain a randomized distributed protocol with an expected competitive ratio of O(log n) on general network topologies with n processors. From a technical point of view, our main result is that Gnn optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of Omega(max {k, log n/log log n}) on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.
Cite as

Abdolhamid Ghodselahi, Fabian Kuhn, and Volker Turau. Concurrent Distributed Serving with Mobile Servers. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ghodselahi_et_al:LIPIcs.ISAAC.2019.53,
  author =	{Ghodselahi, Abdolhamid and Kuhn, Fabian and Turau, Volker},
  title =	{{Concurrent Distributed Serving with Mobile Servers}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{53:1--53:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.53},
  URN =		{urn:nbn:de:0030-drops-115497},
  doi =		{10.4230/LIPIcs.ISAAC.2019.53},
  annote =	{Keywords: Distributed online resource allocation, Distributed directory, Asynchronous communication, Amortized analysis, Tree embeddings}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.15
Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles

Authors: Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In this paper we give sublinear-time distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be listed in sublinear time, O(n^{5/6+o(1)}) rounds and O(n^{21/22+o(1)}) rounds, respectively. Prior to our work, it was not known whether it was possible to even check if the network contains a 4-clique or a 5-clique in sublinear time. For even-length cycles, C_{2k}, we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from O~(n^{5/6}) to O~(n^{3/4}) rounds. We also show two obstacles on proving lower bounds for C_{2k}-freeness: First, we use the new connection to extremal combinatorics to show that the current lower bound of Omega~(sqrt{n}) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant delta in (0,1/2) such that for any k, a Omega(n^{1/2+delta}) lower bound on C_{2k}-freeness implies new lower bounds in circuit complexity. For general subgraphs, it was shown in [Orr Fischer et al., 2018] that for any fixed k, there exists a subgraph H of size k such that H-freeness requires Omega~(n^{2-Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in O(n^{2 - Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].
Cite as

Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.DISC.2019.15,
  author =	{Eden, Talya and Fiat, Nimrod and Fischer, Orr and Kuhn, Fabian and Oshman, Rotem},
  title =	{{Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.15},
  URN =		{urn:nbn:de:0030-drops-113224},
  doi =		{10.4230/LIPIcs.DISC.2019.15},
  annote =	{Keywords: Distributed Computing, Subgraph Freeness, CONGEST}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.144
Optimal Strategies for Patrolling Fences

Authors: Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, and Pascal Pfister

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
A classical multi-agent fence patrolling problem asks: What is the maximum length L of a line fence that k agents with maximum speeds v_1,..., v_k can patrol if each point on the line needs to be visited at least once every unit of time. It is easy to see that L = alpha sum_{i=1}^k v_i for some efficiency alpha in [1/2,1). After a series of works [Czyzowicz et al., 2011; Dumitrescu et al., 2014; Kawamura and Kobayashi, 2015; Kawamura and Soejima, 2015] giving better and better efficiencies, it was conjectured by Kawamura and Soejima [Kawamura and Soejima, 2015] that the best possible efficiency approaches 2/3. No upper bounds on the efficiency below 1 were known. We prove the first such upper bounds and tightly bound the optimal efficiency in terms of the minimum speed ratio s = {v_{max}}/{v_{min}} and the number of agents k. Our bounds of alpha <= 1/{1 + 1/s} and alpha <= 1 - 1/(sqrt{k)+1} imply that in order to achieve efficiency 1 - epsilon, at least k >= Omega(epsilon^{-2}) agents with a speed ratio of s >= Omega(epsilon^{-1}) are necessary. Guided by our upper bounds, we construct a scheme whose efficiency approaches 1, disproving the conjecture stated above. Our scheme asymptotically matches our upper bounds in terms of the maximal speed difference and the number of agents used. A variation of the fence patrolling problem considers a circular fence instead and asks for its circumference to be maximized. We consider the unidirectional case of this variation, where all agents are only allowed to move in one direction, say clockwise. At first, a strategy yielding L = max_{r in [k]} r * v_r where v_1 >= v_2 >= ... >= v_k was conjectured to be optimal by Czyzowicz et al. [Czyzowicz et al., 2011] This was proven not to be the case by giving constructions for only specific numbers of agents with marginal improvements of L. We give a general construction that yields L = 1/{33 log_e log_2(k)} sum_{i=1}^k v_i for any set of agents, which in particular for the case 1, 1/2, ..., 1/k diverges as k - > infty, thus resolving a conjecture by Kawamura and Soejima [Kawamura and Soejima, 2015] affirmatively.
Cite as

Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, and Pascal Pfister. Optimal Strategies for Patrolling Fences. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 144:1-144:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.ICALP.2019.144,
  author =	{Haeupler, Bernhard and Kuhn, Fabian and Martinsson, Anders and Petrova, Kalina and Pfister, Pascal},
  title =	{{Optimal Strategies for Patrolling Fences}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{144:1--144:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.144},
  URN =		{urn:nbn:de:0030-drops-107202},
  doi =		{10.4230/LIPIcs.ICALP.2019.144},
  annote =	{Keywords: multi-agent systems, patrolling algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.6
Distributed Approximate Maximum Matching in the CONGEST Model

Authors: Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We study distributed algorithms for the maximum matching problem in the CONGEST model, where each message must be bounded in size. We give new deterministic upper bounds, and a new lower bound on the problem. We begin by giving a distributed algorithm that computes an exact maximum (unweighted) matching in bipartite graphs, in O(n log n) rounds. Next, we give a distributed algorithm that approximates the fractional weighted maximum matching problem in general graphs. In a graph with maximum degree at most Delta, the algorithm computes a (1-epsilon)-approximation for the problem in time O(log(Delta W)/epsilon^2), where W is a bound on the ratio between the largest and the smallest edge weight. Next, we show a slightly improved and generalized version of the deterministic rounding algorithm of Fischer [DISC '17]. Given a fractional weighted maximum matching solution of value f for a given graph G, we show that in time O((log^2(Delta)+log^*n)/epsilon), the fractional solution can be turned into an integer solution of value at least (1-epsilon)f for bipartite graphs and (1-epsilon) * (g-1)/g * f for general graphs, where g is the length of the shortest odd cycle of G. Together with the above fractional maximum matching algorithm, this implies a deterministic algorithm that computes a (1-epsilon)* (g-1)/g-approximation for the weighted maximum matching problem in time O(log(Delta W)/epsilon^2 + (log^2(Delta)+log^* n)/epsilon). On the lower-bound front, we show that even for unweighted fractional maximum matching in bipartite graphs, computing an (1 - O(1/sqrt{n}))-approximate solution requires at least Omega~(D+sqrt{n}) rounds in CONGEST. This lower bound requires the introduction of a new 2-party communication problem, for which we prove a tight lower bound.
Cite as

Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed Approximate Maximum Matching in the CONGEST Model. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.DISC.2018.6,
  author =	{Ahmadi, Mohamad and Kuhn, Fabian and Oshman, Rotem},
  title =	{{Distributed Approximate Maximum Matching in the CONGEST Model}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.6},
  URN =		{urn:nbn:de:0030-drops-97950},
  doi =		{10.4230/LIPIcs.DISC.2018.6},
  annote =	{Keywords: distributed graph algorithms, maximum matching, deterministic rounding, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.29
Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set

Authors: Mohsen Ghaffari and Fabian Kuhn

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
This paper presents improved deterministic distributed algorithms, with O(log n)-bit messages, for some basic graph problems. The common ingredient in our results is a deterministic distributed algorithm for computing a certain hitting set, which can replace the random part of a number of standard randomized distributed algorithms. This deterministic hitting set algorithm itself is derived using a simple method of conditional expectations. As one main end-result of this derandomized hitting set, we get a deterministic distributed algorithm with round complexity 2^O(sqrt{log n * log log n}) for computing a (2k-1)-spanner of size O~(n^{1+1/k}). This improves considerably on a recent algorithm of Grossman and Parter [DISC'17] which needs O(n^{1/2-1/k} * 2^k) rounds. We also get a 2^O(sqrt{log n * log log n})-round deterministic distributed algorithm for computing an O(log^2 n)-approximation of minimum dominating set; all prior algorithms for this problem were either randomized or required large messages.
Cite as

Mohsen Ghaffari and Fabian Kuhn. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2018.29,
  author =	{Ghaffari, Mohsen and Kuhn, Fabian},
  title =	{{Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.29},
  URN =		{urn:nbn:de:0030-drops-98181},
  doi =		{10.4230/LIPIcs.DISC.2018.29},
  annote =	{Keywords: Distributed Algorithms, Derandomization, Spanners, Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.30
Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping

Authors: Mohsen Ghaffari and Fabian Kuhn

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We present a distributed minimum spanning tree algorithm with near-optimal round complexity of O~(D+sqrt{n}) and message complexity O~(min{n^{3/2}, m}). This is the first algorithm with sublinear message complexity and near-optimal round complexity and it improves over the recent algorithms of Elkin [PODC'17] and Pandurangan et al. [STOC'17], which have the same round complexity but message complexity O~(m). Our method also gives the first broadcast algorithm with o(n) time complexity - when that is possible at all, i.e., when D=o(n) - and o(m) messages. Moreover, our method leads to an O~(sqrt{nD})-round GOSSIP algorithm with bounded-size messages. This is the first such algorithm with a sublinear round complexity.
Cite as

Mohsen Ghaffari and Fabian Kuhn. Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2018.30,
  author =	{Ghaffari, Mohsen and Kuhn, Fabian},
  title =	{{Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{30:1--30:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.30},
  URN =		{urn:nbn:de:0030-drops-98194},
  doi =		{10.4230/LIPIcs.DISC.2018.30},
  annote =	{Keywords: Distributed Algorithms, Minimum Spanning Tree, Round Complexity, Message Complexity, Gossiping, Broadcast}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.42
Brief Announcement: Local Distributed Algorithms in Highly Dynamic Networks

Authors: Philipp Bamberger, Fabian Kuhn, and Yannic Maus

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. We require two properties from our algorithms: (1) They should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and they coincide with the definition of the static graph problem if no topological change appeared recently. (2) If a constant neighborhood around some part of the graph is stable during an interval, the algorithms quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph, namely (degree+1)-vertex coloring and maximal independent set (MIS).
Cite as

Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Brief Announcement: Local Distributed Algorithms in Highly Dynamic Networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 42:1-42:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bamberger_et_al:LIPIcs.DISC.2018.42,
  author =	{Bamberger, Philipp and Kuhn, Fabian and Maus, Yannic},
  title =	{{Brief Announcement: Local Distributed Algorithms in Highly Dynamic Networks}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{42:1--42:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.42},
  URN =		{urn:nbn:de:0030-drops-98318},
  doi =		{10.4230/LIPIcs.DISC.2018.42},
  annote =	{Keywords: dynamic networks, distributed graph algorithms, MIS, vertex coloring}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.52
Shape Recognition by a Finite Automaton Robot

Authors: Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, and Christian Scheideler

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Motivated by the problem of shape recognition by nanoscale computing agents, we investigate the problem of detecting the geometric shape of a structure composed of hexagonal tiles by a finite-state automaton robot. In particular, in this paper we consider the question of recognizing whether the tiles are assembled into a parallelogram whose longer side has length l = f(h), for a given function f(*), where h is the length of the shorter side. To determine the computational power of the finite-state automaton robot, we identify functions that can or cannot be decided when the robot is given a certain number of pebbles. We show that the robot can decide whether l = ah+b for constant integers a and b without any pebbles, but cannot detect whether l = f(h) for any function f(x) = omega(x). For a robot with a single pebble, we present an algorithm to decide whether l = p(h) for a given polynomial p(*) of constant degree. We contrast this result by showing that, for any constant k, any function f(x) = omega(x^(6k + 2)) cannot be decided by a robot with k states and a single pebble. We further present exponential functions that can be decided using two pebbles. Finally, we present a family of functions f_n(*) such that the robot needs more than n pebbles to decide whether l = f_n(h).
Cite as

Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, and Christian Scheideler. Shape Recognition by a Finite Automaton Robot. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gmyr_et_al:LIPIcs.MFCS.2018.52,
  author =	{Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian},
  title =	{{Shape Recognition by a Finite Automaton Robot}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.52},
  URN =		{urn:nbn:de:0030-drops-96347},
  doi =		{10.4230/LIPIcs.MFCS.2018.52},
  annote =	{Keywords: finite automata, shape recognition, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.3
Broadcasting in an Unreliable SINR Model

Authors: Fabian Kuhn and Philipp Schneider

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We investigate distributed algorithms for broadcasting in unreliable wireless networks. Our basic setting is the signal to noise and interference ratio (SINR) model, which captures the physical key characteristics of wireless communication. We consider a dynamic variant of this model in which an adversary can adaptively control the model parameters for each individual transmission. Moreover, we assume that the network devices have no information about the geometry or the topology of the network and do neither know the exact model parameters nor do they have any control over them. Our model is intended to capture the inherently unstable and unreliable nature of real wireless transmission, where signal quality and reception depends on many different aspects that are often hard to measure or predict. We show that with moderate adaptations, the broadcast algorithm of Daum et al. [DISC 13] also works in such an adversarial, much more dynamic setting. The algorithm allows to broadcast a single message in a network of size n in time O(D·polylog(n+R)), where D is the diameter and R describes the granularity of the communication graph.
Cite as

Fabian Kuhn and Philipp Schneider. Broadcasting in an Unreliable SINR Model. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kuhn_et_al:LIPIcs.OPODIS.2017.3,
  author =	{Kuhn, Fabian and Schneider, Philipp},
  title =	{{Broadcasting in an Unreliable SINR Model}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.3},
  URN =		{urn:nbn:de:0030-drops-86247},
  doi =		{10.4230/LIPIcs.OPODIS.2017.3},
  annote =	{Keywords: radio networks, wireless networks, broadcast, SINR model, unreliable communication, dynamic networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.19
Improved Distributed Degree Splitting and Edge Coloring

Authors: Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.
Cite as

Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved Distributed Degree Splitting and Edge Coloring. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.19,
  author =	{Ghaffari, Mohsen and Hirvonen, Juho and Kuhn, Fabian and Maus, Yannic and Suomela, Jukka and Uitto, Jara},
  title =	{{Improved Distributed Degree Splitting and Edge Coloring}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.19},
  URN =		{urn:nbn:de:0030-drops-79794},
  doi =		{10.4230/LIPIcs.DISC.2017.19},
  annote =	{Keywords: Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.22
Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks

Authors: Abdolhamid Ghodselahi and Fabian Kuhn

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem by using path reversal on a pre-computed spanning tree (or any other tree topology simulated on top of the given network). It is known that the Arrow protocol solves the problem with a competitive ratio of O(log D) on trees of diameter D. This implies a distributed queueing algorithm with competitive ratio O(s log D) for general networks with a spanning tree of diameter D and stretch s. In this work we show that when running the Arrow protocol on top of the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC'03], we obtain a randomized distributed online queueing algorithm with expected competitive ratio O(log n) against an oblivious adversary even on general n-node network topologies. The result holds even if the queueing requests occur in an arbitrarily dynamic and concurrent fashion and even if communication is asynchronous. The main technical result of the paper shows that the competitive ratio of the Arrow protocol is constant on a special family of tree topologies, known as hierarchically well separated trees.
Cite as

Abdolhamid Ghodselahi and Fabian Kuhn. Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ghodselahi_et_al:LIPIcs.DISC.2017.22,
  author =	{Ghodselahi, Abdolhamid and Kuhn, Fabian},
  title =	{{Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.22},
  URN =		{urn:nbn:de:0030-drops-79857},
  doi =		{10.4230/LIPIcs.DISC.2017.22},
  annote =	{Keywords: Arrow protocol, competitive analysis, distributed queueing, shared objects, tree embeddings}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.25
An Efficient Communication Abstraction for Dense Wireless Networks

Authors: Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware. After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density.
Cite as

Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. An Efficient Communication Abstraction for Dense Wireless Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.DISC.2017.25,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Kuhn, Fabian and Lynch, Nancy and Newport, Calvin},
  title =	{{An Efficient Communication Abstraction for Dense Wireless Networks}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.25},
  URN =		{urn:nbn:de:0030-drops-79898},
  doi =		{10.4230/LIPIcs.DISC.2017.25},
  annote =	{Keywords: wireless networks, abstractions, SINR, signal fading}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ICALP.2017
LIPIcs, Volume 80, ICALP'17, Complete Volume

Authors: Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
LIPIcs, Volume 80, ICALP'17, Complete Volume
Cite as

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2017,
  title =	{{LIPIcs, Volume 80, ICALP'17, Complete Volume}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017},
  URN =		{urn:nbn:de:0030-drops-75107},
  doi =		{10.4230/LIPIcs.ICALP.2017},
  annote =	{Keywords: Theory of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICALP.2017.0
Front Matter, Table of Contents, Preface, Organization, List of Authors

Authors: Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Front Matter, Table of Contents, Preface, Organization, List of Authors
Cite as

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 0:i-0:xlii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2017.0,
  author =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  title =	{{Front Matter, Table of Contents, Preface, Organization, List of Authors}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{0:i--0:xlii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.0},
  URN =		{urn:nbn:de:0030-drops-73663},
  doi =		{10.4230/LIPIcs.ICALP.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Organization, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.7
The Cost of Global Broadcast in Dynamic Radio Networks

Authors: Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, and Anisur Rahaman Molla

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
We study the single-message broadcast problem in dynamic radio networks. We show that the time complexity of the problem depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. More formally, we model communication using the standard graph-based radio network model. To model the dynamic network, we use a variant of the synchronous dynamic graph model introduced in [Kuhn et al., STOC 2010]. For integer parameters T >= 1 and k => 1, we call a dynamic graph T-interval k-connected if for every interval of T consecutive rounds, there exists a k-vertex-connected stable subgraph. Further, for an integer parameter tau >= 0, we say that the adversary providing the dynamic network is tau-oblivious if for constructing the graph of some round t, the adversary has access to all the randomness (and states) of the algorithm up to round t-tau. As our main result, we show that for any T >= 1, any k >= 1, and any tau = 1, for a tau-oblivious adversary, there is a distributed algorithm to broadcast a single message in time O((1+n/(k * min(tau,T)) * n *log^3(n)). We further show that even for large interval k-connectivity, efficient broadcast is not possible for the usual adaptive adversaries. For a 1-oblivious adversary, we show that even for any T <= (n/k)^{1-epsilon} (for any constant epsilon > 0) and for any k >= 1, global broadcast in T-interval k-connected networks requires at least Omega(n^2/k^2*log(n)) time. Further, for a 0-oblivious adversary, broadcast cannot be solved in T-interval k-connected networks as long as T < n-k.
Cite as

Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, and Anisur Rahaman Molla. The Cost of Global Broadcast in Dynamic Radio Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.OPODIS.2015.7,
  author =	{Ahmadi, Mohamad and Ghodselahi, Abdolhamid and Kuhn, Fabian and Molla, Anisur Rahaman},
  title =	{{The Cost of Global Broadcast in Dynamic Radio Networks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.7},
  URN =		{urn:nbn:de:0030-drops-65989},
  doi =		{10.4230/LIPIcs.OPODIS.2015.7},
  annote =	{Keywords: radio network, dynamic network, global broadcast, interval connectivity, hitting game}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.10
Distributed Sparse Cut Approximation

Authors: Fabian Kuhn and Anisur Rahaman Molla

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
We study the problem of computing a sparse cut in an undirected network graph G=(V,E). We measure the sparsity of a cut (S,V\S) by its conductance phi(S), i.e., by the ratio of the number of edges crossing the cut and the sum of the degrees on the smaller of the two sides. We present an efficient distributed algorithm to compute a cut of low conductance. Specifically, given two parameters b and phi, if there exists a cut of balance at least b and conductance at most phi, our algorithm outputs a cut of balance at least b/2 and conductance at most ~O(sqrt{phi}), where ~O(.) hides polylogarithmic factors in the number of nodes n. Our distributed algorithm works in the \congest model, i.e., it only requires to send messages of size at most O(log(n)) bits. The time complexity of the algorithm is ~O(D + 1/b*phi), where D is the diameter of G. This is a significant improvement over a result by Das Sarma et al. [ICDCN 2015], where it is shown that a cut of the same quality can be computed in time ~O(n + 1/b*phi). The improved running time is in particular achieved by devising and applying an efficient distributed algorithm for the all-prefix-sums problem in a distributed search tree. This algorithm, which is based on the classic parallel all-prefix-sums algorithm, might be of independent interest.
Cite as

Fabian Kuhn and Anisur Rahaman Molla. Distributed Sparse Cut Approximation. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kuhn_et_al:LIPIcs.OPODIS.2015.10,
  author =	{Kuhn, Fabian and Molla, Anisur Rahaman},
  title =	{{Distributed Sparse Cut Approximation}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.10},
  URN =		{urn:nbn:de:0030-drops-66014},
  doi =		{10.4230/LIPIcs.OPODIS.2015.10},
  annote =	{Keywords: sparsest cut, conductance, random walks, all-prefix-sums}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1852
Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time

Authors: Fabian Kuhn

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We are given a set $V$ of autonomous agents (e.g.\ the computers of a distributed system) that are connected to each other by a graph $G=(V,E)$ (e.g.\ by a communication network connecting the agents). Assume that all agents have a unique ID between $1$ and $N$ for a parameter $N\ge|V|$ and that each agent knows its ID as well as the IDs of its neighbors in $G$. Based on this limited information, every agent $v$ must autonomously compute a set of colors $S_v\subseteq C$ such that the color sets $S_u$ and $S_v$ of adjacent agents $u$ and $v$ are disjoint. We prove that there is a deterministic algorithm that uses a total of $|C|=\ensuremath{\mathcal{O}}(\Delta^2\log(N)/\ensuremath{\varepsilon}^2)$ colors such that for every node $v$ of $G$ (i.e., for every agent), we have $|S_v|\ge |C|\cdot(1-\ensuremath{\varepsilon})/(\delta_v+1)$, where $\delta_v$ is the degree of $v$ and where $\Delta$ is the maximum degree of $G$. For $N=\Omega(\Delta^2\log\Delta)$, $\Omega(\Delta^2+\log\log N)$ colors are necessary even to assign at least one color to every node (i.e., to compute a standard vertex coloring). Using randomization, it is possible to assign an $(1-\ensuremath{\varepsilon})/(\delta+1)$-fraction of all colors to every node of degree $\delta$ using only $\ensuremath{\mathcal{O}}(\Delta\log|V|/\ensuremath{\varepsilon}^2)$ colors w.h.p. We show that this is asymptotically almost optimal. For graphs with maximum degree $\Delta=\Omega(\log|V|)$, $\Omega(\Delta\log|V|/\log\log|V|)$ colors are needed in expectation, even to compute a valid coloring. The described multicoloring problem has direct applications in the context of wireless ad hoc and sensor networks. In order to coordinate the access to the shared wireless medium, the nodes of such a network need to employ some medium access control (MAC) protocol. Typical MAC protocols control the access to the shared channel by time (TDMA), frequency (FDMA), or code division multiple access (CDMA) schemes. Many channel access schemes assign a fixed set of time slots, frequencies, or (orthogonal) codes to the nodes of a network such that nodes that interfere with each other receive disjoint sets of time slots, frequencies, or code sets. Finding a valid assignment of time slots, frequencies, or codes hence directly corresponds to computing a multicoloring of a graph $G$. The scarcity of bandwidth, energy, and computing resources in ad hoc and sensor networks, as well as the often highly dynamic nature of these networks require that the multicoloring can be computed based on as little and as local information as possible.
Cite as

Fabian Kuhn. Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 613-624, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kuhn:LIPIcs.STACS.2009.1852,
  author =	{Kuhn, Fabian},
  title =	{{Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{613--624},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1852},
  URN =		{urn:nbn:de:0030-drops-18525},
  doi =		{10.4230/LIPIcs.STACS.2009.1852},
  annote =	{Keywords: Distributed algorithms, Graph coloring, Local algorithms, Medium access control, Multicoloring, TDMA, Wireless networks}
}
Document
DOI: 10.4230/DagSemProc.06131.5
Taming Dynamic and Selfish Peers

Authors: Stefan Schmid, Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer

Published in: Dagstuhl Seminar Proceedings, Volume 6131, Peer-to-Peer-Systems and -Applications (2006)

Abstract
Peer-to-peer systems are often faced with the problem of frequent membership changes. However, many systems are only proven efficient or correct in static environments. In my talk, I will present techniques to maintain desirable properties of a distributed hash table (low peer degree, low network diameter) in spite of ongoing and concurrent dynamics. I will then go on and study the effect of peers not acting according to our protocols. Concretely, I assume that peers are selfish and choose the behavior which maximizes their utility. I will report on our results concerning the impact of selfishness on the peer-to-peer topology.
Cite as

Stefan Schmid, Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Taming Dynamic and Selfish Peers. In Peer-to-Peer-Systems and -Applications. Dagstuhl Seminar Proceedings, Volume 6131, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schmid_et_al:DagSemProc.06131.5,
  author =	{Schmid, Stefan and Kuhn, Fabian and Moscibroda, Thomas and Wattenhofer, Roger},
  title =	{{Taming Dynamic and Selfish Peers}},
  booktitle =	{Peer-to-Peer-Systems and -Applications},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6131},
  editor =	{Anthony D. Joseph and Ralf Steinmetz and Klaus Wehrle},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06131.5},
  URN =		{urn:nbn:de:0030-drops-6477},
  doi =		{10.4230/DagSemProc.06131.5},
  annote =	{Keywords: Churn, Selfishness, P2P Topologies}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact